package 力扣日常刷题.木23一月.第03天303;

import java.util.HashMap;

/**
 * @author 帅小伙
 * @date 2022/3/3
 * @description
 */
public class Demo24和为k的子数组 {

    // 前缀和
    public int subarraySum(int[] nums, int k) {
        int ans = 0;
        int n = nums.length;
        int[] sum = new int[n+1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];

        for (int l = 0; l <= nums.length; l++) {
            for (int r = l+1; r <= nums.length; r++) {
                if((sum[r] - sum[l]) == k) ans++;
            }
        }
        return ans;
    }


    //两个和的差     同余定理，
    public int subarraySum2(int[] nums, int k) {
        int ans = 0,sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);

        for (int num : nums) {
            sum += num;
            ans += map.getOrDefault((sum - k),0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ans;
    }

}
